package week_05;

public class SplitArray_410 {
    public int splitArray(int[] nums, int m) {
        // 猜一个T 进行贪心验证是否能合法
        // 最后一个合法的T
        int l = 0;
        int r = 0;
        for (int num : nums) {
            l = Math.max(l, num);
            r += num;
        }

        while (l < r) {
            int T = (l + r) / 2;
            System.out.println("l:"+l+":r:"+r+":T:"+T);
            if (isVaild(nums, m, T)) {
                r = T;
            } else {
                l = T + 1;
            }

        }
        return r;

    }

    public boolean isVaild(int[] nums, int m, int T) {
        //分成N组不爆——没超过T
        int groupSum = 0;
        int groupCount = 1;
        for (int i = 0; i < nums.length; i++) {
            if (groupSum + nums[i] <= T) {
                groupSum += nums[i];
            } else {
                groupSum = nums[i];
                groupCount++;
            }
        }
        return groupCount <= m;
    }
}
